1734F - Zeros and Ones - CodeForces Solution

import random

cache = {}

def popcount(n):
    res = 0
    while n:
        res += 1
        n &= n - 1
    return res

def solve(n, k):
    if k == 0:
        return 0
    if k == 1:
        return popcount(n) & 1
    if k % 2 == 1:
        t = solve(n, k - 1)
        x = popcount((k - 1) ^ (n + k - 1)) & 1
                return t + x
    if (n, k) in cache:
        return cache[(n, k)]
    if n % 2 == 0:
        one_cell = 2
        zero_cell = 0
        cnt1 = solve(n // 2, k // 2)
        cnt0 = k // 2 - cnt1
    else:
        one_cell = 0
        zero_cell = 1
        cnt1 = solve(n // 2, k // 2) + solve(n // 2 + 1, k // 2)
        cnt0 = k - cnt1
    res = one_cell * cnt1 + zero_cell * cnt0
        cache[(n, k)] = res
    return res

t = int(input())
for _ in range(t):
    cache.clear()
    n, k = map(int, input().split())
    print(solve(n, k))